import org.junit.Test

//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 104 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 
// 👍 1362 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionLongestValidParentheses {
    @Test
    fun main() {
        println(longestValidParentheses("()(())"))
        println(longestValidParentheses("()"))
        // println(longestValidParentheses(")()())"))
        // println(longestValidParentheses(""))
        println(longestValidParentheses("())"))
        println(longestValidParentheses("(()())"))
        // println(longestValidParentheses(")(((((()())()()))()(()))("))
        // println(longestValidParentheses("((())())(()))(()()(()(()))(()((((()))))))((()())()))()()(()(((((()()()())))()())(()()))((((((())))((()))()()))))(()))())))()))()())((()()))))(()(((((())))))()((()(()(())((((())(())((()()(()())))())(()(())()()))())(()()()))()(((()())(((()()())))(((()()()))(()()))()))()))))))())()()((()(())(()))()((()()()((())))()(((()())(()))())())))(((()))))())))()(())))()())))())()((()))((()))()))(((())((()()()(()((()((())))((()()))())(()()(()))))())((())))(()))()))))))()(()))())(()())))))(()))((())(()((())(((((()()()(()()())))(()())()((()(()()))(()(())((()((()))))))))(()(())()())()(()(()(()))()()()(()()())))(())(()((((()()))())))(())((()(())())))))())()()))(((())))())((()(()))(()()))((())(())))))(()(()((()((()()))))))(()()()(()()()(()(())()))()))(((()(())()())(()))())))(((()))())(()((()))(()((()()()(())()(()())()(())(()(()((((())()))(((()()(((()())(()()()(())()())())(()(()()((()))))()(()))))(((())))()()))(()))((()))))()()))))((((()(())()()()((()))((()))())())(()((()()())))))))()))(((()))))))(()())))(((()))((()))())))(((()(((())))())(()))))(((()(((((((((((((())(((()))((((())())()))())((((())(((())))())(((()))))()())()(())())(()))))()))()()()))(((((())()()((()))())(()))()()(()()))(())(()()))()))))(((())))))((()()(()()()()((())((((())())))))((((((()((()((())())(()((()))(()())())())(()(())(())(()((())((())))(())())))(()()())((((()))))((()(())(()(()())))))))))((()())()()))((()(((()((()))(((((()()()()()(()(()((()(()))(()(()((()()))))()(()()((((((()((()())()))((())()()(((((()(()))))()()((()())((()())()(())((()))()()(()))"))
        // println(longestValidParentheses(")(()(()(((())(((((()()))((((()()(()()())())())()))()()()())(())()()(((()))))()((()))(((())()((()()())((())))(())))())((()())()()((()((())))))((()(((((()((()))(()()(())))((()))()))())"))
        // val s = "((((()())()()))()(()))"
        // if((((()())()()))()(()))
        // println(s.length)
        // println(longestValidParentheses(s))
        //

    }

    fun longestValidParentheses(s: String): Int {
        if ("".equals(s)) {
            return 0
        }
        if (s.length < 2) {
            return 0
        }
        if ("()" == s) {
            return 2
        }
        // 第i个最长的有效字符 ，最大：从第i开始，往前计算
        // 此种推断 ，dp[i] 都是从最右开始的有效
        val dp = IntArray(s.length + 1)
        // dp[0] = 0
        var max = 0
        for (i in 1 until s.length) {
            // dp[i] =
            if (')' == s[i] && '(' == s[i - 1]) {
                // a()
                // 第i位及之前组成一个括号
                val index = i - 2
                if (index >= 0) {
                    dp[i] = dp[index] + 2
                } else {
                    dp[i] = 2
                }
            } else if (')' == s[i]) {
                // 前一位也是 )，判断前一位最长有效后的左边一个是不是 (
                // "())" 导致越界
                // i-1 为左边一个); dp[i-1] 为左边一个(的最长有效长度
                val index = i - 1 - dp[i - 1]
                if (index >= 0 && '(' == s[index]) {
                    // "()(())" ; 此处要加开头的两个括号
                    dp[i] = dp[i - 1] + 2 + if (index - 1 > 0) dp[index - 1] else 0
                } else {
                    dp[i] = 0
                }
            } else {
                dp[i] = 0
            }
            max = max.coerceAtLeast(dp[i])
        }
        return max
        TODO()
    }

}
//leetcode submit region end(Prohibit modification and deletion)
